package demo.practice.top100;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class P22 {

    //["()()()()","(()())()","(()(()))","()()(())","(((())))","(())()()","()((()))","()(())()","()(()())","(()()())","((()()))","((()))()","((())())"]
    //["(((())))","((()()))","((())())","((()))()","(()(()))","(()()())","(()())()","(())(())","(())()()","()((()))","()(()())","()(())()","()()(())","()()()()"]
   /* public List<String> generateParenthesis(int n) {
        if(n<=0) {
            return new ArrayList<>();
        }
        return new ArrayList<>(get(n));
    }

    public Set<String> get(int n) {
        if (n == 1) {
            Set<String> res = new HashSet<>();
            res.add("()");
            return res;
        } else {
            Set<String> set = get(n - 1);
            Set<String>  res = new HashSet<>();
            for (String s : set) {
                res.add("("+s+")");
                res.add("()"+s);
                res.add(s+"()");
            }
            return res;
        }
    }
*/

    public static void main(String[] args) {
        P22 p22 = new P22();
        p22.generateParenthesis(2);
    }

        public List<String> generateParenthesis(int n) {
            if (n <= 0) {
                return new ArrayList<>();
            }
            List<String> res = new ArrayList<>();
            get("", 2 * n, res,0,0);
            return res;
        }

        public void get(String str, int n, List<String> list, int l, int r) {
            if(r>n/2|| r>l || l>n/2  ){
                return;
            }

            if (str.length() == n) {
                list.add(str);
                return;
            }
            get(new String(str + "("), n, list, l + 1, r);
            get(new String(str + ")"), n, list, l, r + 1);
        }
}
